| KD | 您所在的位置：网站首页 › kd trees › KD |
KD
|
三、Kd-Tree的最近邻查找
（1）将查询数据Q从根结点开始，按照Q与各个结点的比较结果向下访问Kd-Tree，直至达到叶子结点。
其中Q与结点的比较指的是将Q对应于结点中的k维度上的值与中值m进行比较，若Q(k) < m，则访问左子树，否则访问右子树。达到叶子结点时，计算Q与叶子结点上保存的数据之间的距离，记录下最小距离对应的数据点，记为当前最近邻点nearest和最小距离dis。
（2）进行回溯操作，该操作是为了找到离Q更近的“最近邻点”。即判断未被访问过的分支里是否还有离Q更近的点，它们之间的距离小于dis。
如果Q与其父结点下的未被访问过的分支之间的距离小于dis，则认为该分支中存在离P更近的数据，进入该结点，进行（1）步骤一样的查找过程，如果找到更近的数据点，则更新为当前的最近邻点nearest，并更新dis。
如果Q与其父结点下的未被访问过的分支之间的距离大于dis，则说明该分支内不存在与Q更近的点。
回溯的判断过程是从下往上进行的，直到回溯到根结点时已经不存在与P更近的分支为止。
注：判断未被访问过的树分支中是否还有离Q更近的点，就是判断"Q与未被访问的树分支的距离|Q(k) - m|"是否小于"Q到当前的最近邻点nearest的距离dis"。从几何空间上来看，就是判断以Q为中心，以dis为半径超球面是否与未被访问的树分支代表的超矩形相交。
下面举两个例子来演示一下最近邻查找的过程。 假设我们的kd树就是上面通过样本集{（2,3），（5,4），（9,6），（4,7），（8,1），（7,2）}创建的。 例1：查找点Q(2.1,3.1) 如下图所示，红色的点即为要查找的点。通过图4二叉搜索，顺着搜索路径很快就能找到当前的最邻近点（2,3）。
图. 5
在上述搜索过程中，产生的搜索路径节点有。为了找到真正的最近邻，还需要进行'回溯'操作，首先以（2,3）作为当前最近邻点nearest，计算其到查询点Q（2.1,3.1）的距离dis为0.1414，然后回溯到其父节点（5,4），并判断在该父节点的其他子节点空间中是否有距离查询点Q更近的数据点。以（2.1,3.1）为圆心，以0.1414为半径画圆，如图6所示。发现该圆并不和超平面y = 4交割，即这里：|Q(k) - m|=|3.1 - 4|=0.9 > 0.1414，因此不用进入（5,4）节点右子空间中去搜索。
图. 6
再回溯到（7,2），以（2.1,3.1）为圆心，以0.1414为半径的圆更不会与x = 7超平面交割，因此不用进入（7,2）右子空间进行查找。至此，搜索路径中的节点已经全部回溯完，结束整个搜索，返回最近邻点（2,3），最近距离为0.1414。
例2：查找点Q(2,4.5) 如下图所示，同样经过图4的二叉搜索，可得当前的最邻近点（4,7），产生的搜索路径节点有。首先以（4,7）作为当前最近邻点nearest，计算其到查询点Q（2,4.5）的距离dis为3.202，然后回溯到其父节点（5,4），并判断在该父节点的其他子节点空间中是否有距离查询点Q更近的数据点。以（2,4.5）为圆心，以为3.202为半径画圆，如图7所示。发现该圆和超平面y = 4交割，即这里：|Q(k) - m|=|4.5 - 4|=0.5 < 3.202，因此进入（5,4）节点右子空间中去搜索。所以，将(2,3)加入到搜索路径中，现在搜索路径节点有。同时，注意：点Q(2,4.5)与父节点(5,4)的距离也要考虑，由于这两点间的距离3.04 < 3.202，所以将(5,4)赋给nearest，并且dist=3.04。
图. 7
接下来，回溯至（2,3）叶子节点，点Q（2,4.5）和（2,3）的距离为1.5，比距离（5,4）要近，所以最近邻点nearest更新为(2,3)，最近距离dis更新为1.5。回溯至（7,2），如图8所示，以（2,4.5）为圆心1.5为半径作圆，并不和x = 7分割超平面交割，即这里：|Q(k) - m|=|2 - 7|=5 > 1.5。至此，搜索路径回溯完。返回最近邻点（2,3），最近距离1.5。 图. 8 四、总结Kd树在维度较小时（比如20、30），算法的查找效率很高，然而当数据维度增大（例如：K≥100），查找效率会随着维度的增加而迅速下降。假设数据集的维数为D，一般来说要求数据的规模N满足N>>2的D次方，才能达到高效的搜索。 为了能够让Kd树满足对高维数据的索引，Jeffrey S. Beis和David G. Lowe提出了一种改进算法——Kd-tree with BBF（Best Bin First），该算法能够实现近似K近邻的快速搜索，在保证一定查找精度的前提下使得查找速度较快。
|
【本文地址】
公司简介
联系我们